package chapter2.src.com.kkb.array;


import lombok.Data;

/**
 * modifier  : wushikai
 * <p>
 * date : 2021-03-15
 * https://www.cnblogs.com/skywang12345/p/3577479.html 参考
 */
@Data
public class AVLTree {


    public AVLTreeNode mRoot;    // 根结点


    // AVL树的节点(内部类)
    class AVLTreeNode {
        Integer key;            // 关键字(键值)
        int height;             // 高度
        AVLTreeNode left;       // 左孩子
        AVLTreeNode right;     // 右孩子

        public AVLTreeNode(Integer key, AVLTreeNode left, AVLTreeNode right) {
            this.key = key;
            this.left = left;
            this.right = right;
            this.height = 0;
        }
    }

    /**
     * @return  获取树的高度, 如果空 , 返回 0
     */
    public int height(AVLTreeNode tree) {
        if (tree != null)
            return tree.height;

        return 0;
    }

    public int height() {
        return height(mRoot);
    }


    /**
     * 比较两个值的大小
     */
    public int max(int a, int b) {
        return a > b ? a : b;
    }


    /**
     * LL：左左对应的情况(左单旋转)。
     * <p>
     * 返回值：旋转后的根节点
     */
    public AVLTreeNode leftLeftRotation(AVLTreeNode k2) {
        System.out.println("LL 旋转被调用");
        AVLTreeNode k1;

        k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;

        k2.height = max(height(k2.left), height(k2.right)) + 1;
        k1.height = max(height(k1.left), k2.height) + 1;

        return k1;
    }

    /**
     * RR：右右对应的情况(右单旋转)。
     * <p>
     * 返回值：旋转后的根节点
     */
    public AVLTreeNode rightRightRotation(AVLTreeNode k1) {
        AVLTreeNode k2;

        k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;

        k1.height = max(height(k1.left), height(k1.right)) + 1;
        k2.height = max(height(k2.right), k1.height) + 1;

        return k2;
    }


    /**
     * LR：左右对应的情况(左双旋转)。
     * <p>
     * 返回值：旋转后的根节点
     */
    public AVLTreeNode leftRightRotation(AVLTreeNode k3) {
        System.out.println("LR型 旋转被调用");
        k3.left = rightRightRotation(k3.left);

        return leftLeftRotation(k3);
    }


    /**
     * 前序遍历"AVL树"
     */
    public void preOrder(AVLTreeNode tree) {
        if (tree != null) {
            System.out.print(tree.key + " ");
            preOrder(tree.left);
            preOrder(tree.right);
        }
    }

    /**
     * 前序遍历首先访问根结点然后遍历左子树，最后遍历右子树
     *
     * */
    public void preOrder() {
        preOrder(mRoot);
    }


    /**
     * RL：右左对应的情况(右双旋转)。
     * <p>
     * 返回值：旋转后的根节点
     */
    public AVLTreeNode rightLeftRotation(AVLTreeNode k1) {
        k1.right = leftLeftRotation(k1.right);

        return rightRightRotation(k1);
    }

    public void insert(int key) {
        mRoot = insert(mRoot, key);
    }

    /**
     * 难点之一;
     * 有 4 总调节情况;   最难的是判断 到底 往哪里调节 ;
     * 将结点插入到AVL树中，并返回根节点, 假设是理想情况, 即: key 都是不同的;
     * @param   tree AVL树的根结点
     * @param   key 插入的结点的键值
     * @return  根节点
     */
    public AVLTreeNode insert(AVLTreeNode tree, int  key) {

        if (tree == null) {

            tree = new AVLTreeNode(key, null, null);    // 新建节点

        } else {
            int cmp = compareTo( key, tree.key);   //判断 往 那边插入节点 是左 还是  右

            if (cmp < 0) {    // 应该将key插入到"tree的左子树"的情况
                tree.left = insert(tree.left, key);
                // 插入节点后，若AVL树失去平衡，则进行相应的调节。
                if (height(tree.left) - height(tree.right) == 2) {   // 两边高度相差不大, 则没有必要 矫正
                    if (compareTo(key, tree.left.key) < 0)
                        tree = leftLeftRotation(tree);
                    else
                        tree = leftRightRotation(tree);
                }
            } else if (cmp > 0) {    // 应该将key插入到"tree的右子树"的情况
                tree.right = insert(tree.right, key);
                // 插入节点后，若AVL树失去平衡，则进行相应的调节。
                if (height(tree.right) - height(tree.left) == 2) {
                    if ( compareTo(key, tree.right.key) > 0)
                        tree = rightRightRotation(tree);
                    else
                        tree = rightLeftRotation(tree);
                }
            }
        }

        tree.height = max(height(tree.left), height(tree.right)) + 1; //更新树的高度;
        System.out.println("节点 " + tree.key +" 的高度变成了 " +  tree.height );
        return tree;
    }

    /**
     * var1 > var2 return  1
     * <p>
     * var1 < var2 return -1
     *
     * */
    public int compareTo(int var1, int var2){

        if (var1> var2){
            return 1;
        }else{
             return -1;
        }
    }


    /**
     * 查找最大结点：返回tree为根结点的AVL树的最大结点。
     */

    public AVLTreeNode maximum(AVLTreeNode tree) {
        if (tree == null)
            return null;

        while (tree.right != null)
            tree = tree.right;
        return tree;
    }

    public Integer maximum() {
        AVLTreeNode p = maximum(mRoot);
        if (p != null)
            return p.key;

        return null;
    }


    /**
     * 删除结点(z)，返回根节点
     * <p>
     * 参数说明：
     * tree AVL树的根结点
     * z 待删除的结点
     * 返回值：
     * 根节点
     */
    public AVLTreeNode remove(AVLTreeNode tree, AVLTreeNode z) {
        // 根为空 或者 没有要删除的节点，直接返回null。
        if (tree == null || z == null)
            return null;

        int cmp = z.key.compareTo(tree.key);
        if (cmp < 0) {        // 待删除的节点在"tree的左子树"中
            tree.left = remove(tree.left, z);
            // 删除节点后，若AVL树失去平衡，则进行相应的调节。
            if (height(tree.right) - height(tree.left) == 2) {
                AVLTreeNode r = tree.right;
                if (height(r.left) > height(r.right))
                    tree = rightLeftRotation(tree);
                else
                    tree = rightRightRotation(tree);
            }
        } else if (cmp > 0) {    // 待删除的节点在"tree的右子树"中
            tree.right = remove(tree.right, z);
            // 删除节点后，若AVL树失去平衡，则进行相应的调节。
            if (height(tree.left) - height(tree.right) == 2) {
                AVLTreeNode l = tree.left;
                if (height(l.right) > height(l.left))
                    tree = leftRightRotation(tree);
                else
                    tree = leftLeftRotation(tree);
            }
        } else {    // tree是对应要删除的节点。
            // tree的左右孩子都非空
            if ((tree.left != null) && (tree.right != null)) {
                if (height(tree.left) > height(tree.right)) {
                    // 如果tree的左子树比右子树高；
                    // 则(01)找出tree的左子树中的最大节点
                    //   (02)将该最大节点的值赋值给tree。
                    //   (03)删除该最大节点。
                    // 这类似于用"tree的左子树中最大节点"做"tree"的替身；
                    // 采用这种方式的好处是：删除"tree的左子树中最大节点"之后，AVL树仍然是平衡的。
                    AVLTreeNode max = maximum(tree.left);
                    tree.key = max.key;
                    tree.left = remove(tree.left, max);
                } else {
                    // 如果tree的左子树不比右子树高(即它们相等，或右子树比左子树高1)
                    // 则(01)找出tree的右子树中的最小节点
                    //   (02)将该最小节点的值赋值给tree。
                    //   (03)删除该最小节点。
                    // 这类似于用"tree的右子树中最小节点"做"tree"的替身；
                    // 采用这种方式的好处是：删除"tree的右子树中最小节点"之后，AVL树仍然是平衡的。
                    AVLTreeNode min = maximum(tree.right);
                    tree.key = min.key;
                    tree.right = remove(tree.right, min);
                }
            } else {
                AVLTreeNode tmp = tree;
                tree = (tree.left != null) ? tree.left : tree.right;
                tmp = null;
            }
        }

        return tree;
    }


    public AVLTreeNode search(Integer key) {
        return search(mRoot, key);
    }

    public void remove(Integer key) {
        AVLTreeNode z;

        if ((z = search(mRoot, key)) != null)
            mRoot = remove(mRoot, z);
    }


    /**
     * (递归实现)查找"AVL树x"中键值为key的节点
     */
    public AVLTreeNode search(AVLTreeNode x, Integer key) {
        if (x == null)
            return x;

        int cmp = key.compareTo(x.key);
        if (cmp < 0)
            return search(x.left, key);
        else if (cmp > 0)
            return search(x.right, key);
        else
            return x;
    }


    /**
     * 打印"二叉查找树"
     * <p>
     * key        -- 节点的键值
     * direction  --  0，表示该节点是根节点;
     * -1，表示该节点是它的父结点的左孩子;
     * 1，表示该节点是它的父结点的右孩子。
     */
    public void print(AVLTreeNode tree, Integer key, int direction) {
        if (tree != null) {
            if (direction == 0)    // tree是根节点
                System.out.printf("%2d is root\n", tree.key, key);
            else                // tree是分支节点
                System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction == 1 ? "right" : "left");

            print(tree.left, tree.key, -1);
            print(tree.right, tree.key, 1);
        }
    }

    public void print() {
        if (mRoot != null)
            print(mRoot, mRoot.key, 0);
    }


    /**
     *       3
     *      /     ---> ll 向右转 -->   2
     *     2                        /  \
     *    /                        1   3
     *   1
     * */
    public  static void simpleDemoLLNotBalance ( ){

        int arr[] = {3, 2, 1};
        AVLTree tree = new AVLTree();
        for (int i = 0; i < arr.length; i++) {

            tree.insert(arr[i]);
        }

        System.out.printf("\n== 前序遍历: ");
        tree.preOrder();
    }

    /**
     *
     *              rr型不平衡 向左转
     *   1
     *    \                              2
     *     2          -->              /  \
     *      \                         1   3
     *       3
     * */
    public  static void simpleDemoRRNotBalance ( ){
        int arr[] = {1, 2, 3};
        AVLTree tree = new AVLTree();
        for (int i = 0; i < arr.length; i++) {

            tree.insert(arr[i]);
        }

        System.out.printf("\n== 前序遍历: ");
        tree.preOrder();

    }


    /**
     *
     *                 3
     *               /       ---  设置为ll型不平衡      --> 向右 单转
     *             1
     *              \        ---  设置为rr型不平衡      --> 向左 单转
     *              2
     * */
    public static void simpleDemoLrNotBalance() {

        int arr[] = {3, 1, 2};

        AVLTree tree = new AVLTree();
        for (int i = 0; i < arr.length; i++) {

            tree.insert(arr[i]);
        }

        System.out.printf("\n== 前序遍历: ");
        tree.preOrder();
    }

    public static void main(String[] args){
        simpleDemoLLNotBalance();
    }


    public static void mediumDemo() {

        int arr[] = {3, 2, 1, 4, 5, 6, 7, 16, 15, 14, 13, 12, 11, 10, 8, 9};

        AVLTree tree = new AVLTree();
        System.out.printf("== 依次添加: ");
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("%d ", arr[i]);
            tree.insert(arr[i]);
        }

        System.out.printf("\n== 前序遍历: ");
        tree.preOrder();

        // System.out.printf("\n== 中序遍历: ");
        // tree.inOrder();
//
        // System.out.printf("\n== 后序遍历: ");
        // tree.postOrder();
        System.out.printf("\n");

        System.out.printf("== 高度: %d\n", tree.height());
        // System.out.printf("== 最小值: %d\n", tree.minimum());
        System.out.printf("== 最大值: %d\n", tree.maximum());
        System.out.printf("== 树的详细信息: \n");
        tree.print();


    }


}
